On account of the high degree of integration of electronic circuits, the susceptibility to errors and the frequency of errors in electronic circuits are increasing. In particular, the frequency of non-permanent or transient errors is increasing, these errors having an effect as so-called soft errors in registers. Such soft errors are caused by radiation, for example, and they often affect adjacent bits.
It is known to protect electronic circuits and generally data in data processing by means of codes. The codes used in this case are, for example, the parity bit code, the Hamming code, BCH codes, the Berger code (see, for example, Berger, J. M.: “A Note on Error Detection Codes for Asymetric Channels”, Information and Control, Vol. 4, 1961, pp. 68-73) and the Bose-Lin code (see, for example, Lin et al.: “Error Control Coding, Fundamentals and Applications”, Prentice Hall, 1983; Bose et al.: “Systematic Unidirectional Error Detecting Codes”, IEEE Trans. Computers, C34, 1026-1032, 1985).
In a circuit for implementing the parity bit code, the n information or data bits, where n is greater than or equal to 2, are logically combined by XOR gates in a parity tree to form a single additional parity bit, that is to say a single check bit. An error in an individual bit, or in an odd number of data bits, leads to a change in the parity bit and thus to a detection of such an error. What is advantageous about the parity bit code is that only a single additional check bit for error detection has to be added independently to the number n of data bits to be checked. What is disadvantageous is that all errors that corrupt an even number of bits are not detected with this code.
If parity is implemented for a plurality of non-overlapping groups of information bits, then 2-bit errors cannot be detected if they corrupt bits of the same group, which is disadvantageous. All 1-bit errors and all 2-bit errors can be reliably detected using a Hamming code.
What is disadvantageous here, in particular, is that the outlay for realizing error detection by means of a Hamming code is relatively high. In particular, the number m of bits required for error detection increases as the number n of data bits to be monitored increases, which leads to a relatively high outlay, which is disadvantageous. In addition, the Hamming code, as already explained, does not detect all odd errors, which is likewise disadvantageous. Even errors such as 4-bit, 6-bit, . . . errors are detected only in part.
As a generalization of Hamming codes, consideration is given to fire codes and BCH codes, which have better error detection properties than Hamming codes but require an even higher outlay for their realization than Hamming codes.
Berger codes are furthermore known, which detect all unidirectional errors in which the erroneous bits each change in one direction, that is to say that all the erroneous bits change from 0 to 1 or all the erroneous bits change from 1 to 0. In these codes too, the number of additional m check bits required increases as the number of data bits to be monitored increases, which is disadvantageous in particular for large numbers n of data bits. An essential disadvantage is, in particular, that errors in which an identical number of bits change from 0 to 1 and from 1 to 0 cannot be detected. In particular, all bidirectional 2-bit errors, that is to say those 2-bit errors in which a first value 1 changes erroneously to 0 and a second value 0 changes erroneously to 1, cannot be detected, under any circumstances. That even applies to all adjacent 2-bit errors that can often occur, in particular, as soft errors.
An error detecting code having a fixed number m of check bits independently of the number n of data bits is the Bose-Lin code. In the same way as the Berger code, it does not detect all bidirectional 2-bit errors, even if they are adjacent, which is disadvantageous.
U.S. Pat. No. 5,446,745 discloses a device for error correction on an optical storage media. Reed-Solomon errors are dealt with. The various embodiments utilize XOR elements which realize linear Boolean functions. An essential aim in the case of the known device is to reduce the number of XOR elements.
U.S. Pat. No. 4,918,638 discloses a circuit for multiplying two polynomials in a Galois field. In one configuration, the circuit for polynomial multiplication in the Galois field comprises subcircuits (columns) (see FIG. 5 therein).